3-4 1371.每个元音包含偶数次的最长子字符串 Ⅱ

Date：2022-03-06 20:01:10

题目：1371. 每个元音包含偶数次的最长子字符串 Ⅱ ( 中等😕 )

分析

• 暴力法：

  • 时间复杂度O(n^3)

• 前缀和

  前缀和特点

  • 对于一个区间，我们可以用两个前缀和的差值，得到其中某个字母的出现次数

  关于前缀和的解法，可以参考这篇文章：参考官方题解，步步引导，代码实现

  • 时间复杂度O(n)，空间复杂度O(n)

• 前缀和+状态压缩

题解

暴力法

function main() {
  const s = 'eleetminicoworoep'
  // const s = 'leetcodeisgreat'
  // const s = 'bcbcbc'

  console.log('[]:', findTheLongestSubstring(s))
}

main()

function findTheLongestSubstring(s: string): number {
  const len = s.length

  let max = ''
  let evenMap: { [key: string]: number } = {}

  for (let i = 1; i < len; ++i) {
    let current = ''
    resetMap()

    for (let j = i; j >= 0; --j) {
      current = s[j] + current

      if (evenMap[s[j]] != undefined) {
        ++evenMap[s[j]]
      }

      if (isEven() && current.length >= max.length) {
        max = current
      }
    }
  }

  return max.length

  function isEven(): boolean {
    return Object.values(evenMap).every((x) => x % 2 == 0)
  }

  function resetMap() {
    evenMap = {
      a: 0,
      e: 0,
      i: 0,
      o: 0,
      u: 0,
    }
  }
}

前缀和

enum NumType {
  EVEN = '1',
  ODD = '2',
}

class Status {
  private status: {
    [key: string]: NumType
  } = {
    a: NumType.EVEN,
    e: NumType.EVEN,
    i: NumType.EVEN,
    o: NumType.EVEN,
    u: NumType.EVEN,
  }

  invert(who: 'a' | 'e' | 'i' | 'o' | 'u') {
    this.status[who] = this.status[who] == NumType.EVEN ? NumType.ODD : NumType.EVEN
  }

  toString() {
    return Object.keys(this.status)
      .map((key) => key + this.status[key])
      .join('')
  }

  isEqual(newState: { [key: string]: NumType }) {
    const state = this.status
    const keys = Object.keys(state)

    for (let i = 0; i < keys.length; ++i) {
      if (state[i] != newState[i]) return false
    }

    return true
  }
}


function main() {
  // const s = 'eleetminicoworoep'
  // const s = 'leetcodeisgreat'
  const s = 'bcbcbc'

  console.log('[]:', findTheLongestSubstring222(s))
}

main()

function findTheLongestSubstring222(s: string): number {
  const len = s.length

  let res = 0
  const map = new Map<string, number>()
  const currStatus = new Status()

  map.set(currStatus.toString(), -1)

  for (let i = 0; i < len; ++i) {
    const char = s.charAt(i)

    if (char == 'a') {
      currStatus.invert('a')
    } else if (char == 'e') {
      currStatus.invert('e')
    } else if (char == 'i') {
      currStatus.invert('i')
    } else if (char == 'o') {
      currStatus.invert('o')
    } else if (char == 'u') {
      currStatus.invert('u')
    }

    // use status's string as key
    const currKey = currStatus.toString()

    if (map.has(currKey)) {
      res = Math.max(res, i - map.get(currKey))
    } else {
      map.set(currKey, i)
    }
  }

  return res
}